// 题目：给你一个栈，反转这个栈， 反转之后的栈和反转之前的栈 必须是同一个栈
// 参考链接： https://gitee.com/douma_edu/douma_algo_training_camp/issues/I4RW2Y
package main

import "fmt"

// 将栈顶元素放入指定位置
func Insert(stack []int, n int) {
	temp := make([]int, 0)
	// 2. 将栈顶元素拿出来
	bottom := stack[len(stack)-1]
	stack = stack[:len(stack)-1]
	// 1. 利用辅助栈，拿出来上面的 n - 1个元素
	for i := 1; i < n; i++ {
		temp = append(temp, stack[len(stack)-1])
		stack = stack[:len(stack)-1]
	}
	// 3. 栈顶入栈
	stack = append(stack, bottom)
	// 4. 其他元素重新放回 stack中
	for len(temp) > 0 {
		stack = append(stack, temp[len(temp)-1])
		temp = temp[:len(temp)-1]
	}
}

// 实现1， 迭代版本
func reverseStackIter(stack []int) {
	// 取出底部元素， 放到栈顶， 需要进行 n次
	for n := len(stack); n > 0; n-- {
		Insert(stack, n)
	}
	fmt.Println(stack)
}

// 实现2.
// 分析我上面迭代对栈的使用，（以第一步为例子）主要是保存 后面四个元素
// 进入辅助栈， 然后将栈顶元素，先入栈。最后再将辅助栈内的元素依次进栈。完成栈顶到栈底的操作。
// 那么使用系统函数调用栈，也是完成上面辅助栈的功能
func reverseStackIter1(stack []int) []int {
	// 定义变量保存栈顶元素, 及插入时的长度
	var top, length int
	// 定义递归函数实现 栈顶元素插入到某一位置的操作
	var insert1 func(stack []int) []int
	insert1 = func(s []int) []int {
		// 3. 递归终止条件，找到对应位置（之前的元素已进入系统调用栈）
		// 当前元素插入（或者说入栈）
		if len(s) == length {
			s = append(s, top)
			return s
		}
		// 2. 保留栈顶元素
		e := s[len(s)-1]
		s = s[:len(s)-1]
		// 3. 调用递归函数，利用系统栈，保留栈顶元素
		s = insert1(s)
		// 4. 将当前元素再重新入栈
		s = append(s, e)
		return s
	}

	for i, n := 0, len(stack); i < n; i++ {
		// 1. 记录栈顶元素, 该插入的位置
		top, length = stack[len(stack)-1], i
		stack = stack[:len(stack)-1]
		// 2. 调用递归函数
		stack = insert1(stack)
	}
	return stack
}

// 克服上面递归代码中的老是返回切片， 定义一个全局，或者闭包变量就可以了。

func main1() {
	a := []int{1, 2, 3, 4, 5}
	//reverseStackIter(a)    // 函数： removeBottomIter(stack []int) int
	reverseStackIter1(a)
	b := make([]int, 0, 6)
	c := make([]int, 0)
	copy(c, b)
	fmt.Println(cap(c))
	//b := a[:len(a) - 1]
	//b = append(b, 999)
	//fmt.Println(a, b)
	// 执行添加操作
	//b := make([]int, 0, 5)
	//b = append(b, 1)
	//
	//c := b
	//c = append(c, 2)
	//fmt.Println(b, c)
	//b = append(b, 33)
	//fmt.Println(b, c)

	//fmt.Println(cap(a), len(a))
	//b := a
	//a = a[:3]
	//fmt.Println(cap(a), len(a))
	//b = b[:4]
	//b = append(b, 777)
	//b = append(b, 666)
	//fmt.Println(b)
	//fmt.Println(cap(b), len(b))
	//b[1] = 888
	//b = b[:1]
	//b[0] = 999
	//fmt.Println(a, b)
}
